# RSA+Shamir protocol

Нам удалось перехватить сообщения двух злоумышлеников и их протокол. Узнайте, что они передают.

# WriteUp

[Decrypt](decrypt.py)

```python

from Cryptodome.Util.number import long_to_bytes, bytes_to_long

n = 23085624893245749180014300217576230562938421249568552273579092305963682129152487733027041285189115682414809990012729164061666210552008372863875184836643664645600099296399589002370063290902981042659429524890260316912533051639979518152568250828384149083720831428298898278514201627873644102943676546052962354014450752681090756044627952494550872005390297475753921837231825521472922418820153268500177769864302497484001117759877540227021881873074412639452484041064918133830944627818347871304310710035259294858860255150714974274610669048248449564318369420773858635741033508866773784678389750095142010308224842132317132612409
e1 = 14874094470682923337
e2 = 18235496239177365289

C1 = 6194732661899945441314873441276750800928635175358230047860722251027812386312353571409529426731807518511376086779707763990823952570752779845986730096031586969284962069542269974992940735680635851487264977983474747419389670066698247863027768970146148026584121398663239511237514941097591159851891672305761556330432783357511751911635442889662596255508011393506807871742328273690130133198888503199025962626997941407846768128134728126092020765062601547373822305866042754747409106426557191371328362902320936783996198982861759381486166920118627069951943913873905077432011621973257831852075981644593972546508507860399310494451
C12 = 14786315034454851820956798066170791252032859960781383232769623990488889019568042846820290213020137568459693516111303919486948082514324339893675375660736400394644404674732250866195070740399697981242813955762520668068064463511063503719443177916686790694848888366867493050438470658056225245116104422403440798593614854177057971796661779901045056582328028805478964893489850944350531996904392991970132129112041211655570039027175438311376168024773252909643659775276693538185636187534584437871695711626424368863578115814289867895383380403300465813862589242210130050904552086301927251466469439765855531852147690959121755040263
C2 = 5744164165197984067424230388580405709695702766792853966769272474923073059943702387409774578275134880611677469397653118328655824921173109711840161229012657285791297827686553101483068122710542520765659744987610246542213688444026805826754895798054302707571593748322253564588234349091149395735001907734055158531228555373894040246082786340398394896938313994499059795893421443514728654635357583530057502543429364035561560851778513838147168030243569083225016159675995923587885519208078719848714070952693243770710869076056759070550295199822297907167170567563156122305860769347733837825468306795052982083848400312760673045235

def NOD(a, b):
    x, A, B, y, C, D = a, 1, 0, b, 0, 1
    while y != 0:
        q, r = x // y, x % y
        x, A, B, y, C, D = y, C, D, r, A-q*C, B-q*D
    return x, A, B

def main():
    d, a, b = NOD(e1, e2)
    M = (pow(C1, a, n)*pow(C2, b, n)) % n
    FLAG = long_to_bytes(M)
    print(FLAG)

if __name__ == "__main__":
    main()


```

# Flag

RDGCTF{The_RSA_cipher_is_not_suitable_for_this_protocol}